당신의 미션 🎯
2차원 좌표로 주어진 $N$ 개의 행성들을 최소 비용의 "하이퍼 레인" 네트워크로 다시 연결하세요.
- 목표:모든 $N$ 개의 행성(정점)을 연결하여 직접적이거나 간접적으로 모두 접근 가능하게 하세요.
- 목적:전체 비용을 최소화하는 네트워크 설계를 찾아보세요.
분석 🛰️
레인(간선)의 비용은 유클리드 거리입니다:
$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
- 레인은 두 행성 사이에 어떤사이에 건설할 수 있습니다.
- 즉, 우리는 완전(밀집) 그래프를 갖게 됩니다.
해결 방법 ⚙️
이는 전형적인 최소 스패닝 트리(MST)문제입니다.
- 알고리즘: 힌트는 프림 알고리즘($O(V^2)$ 버전)을 추천합니다. 이는 밀집 그래프에 완벽하게 적합합니다.
- 시작점: 알고리즘은 행성 0에서 시작하여 일관된 결과를 얻겠습니다.
완전 그래프(왼쪽)는 모든 가능한 간선을 포함합니다. 반면, 최소 스패닝 트리(MST, 오른쪽)는 모든 정점을 연결하는 가장 저렴한 간선 부분 집합입니다.